package algorithm;

import java.util.*;

/**
 * Created by Administrator on 2017/7/4.
 * 选择问题：N个数中，从大到小顺序，算出第k个元素
 * 并且算出消耗时间
 *
 * 使用两种方案：
 * 一、排序后，选出第k个
 * 二、排序k个元素，在将其他的元素慢慢往里面插
 *
 * 总体来说，由于采用的冒泡排序，效率都比较插。大约在10万个数字时，已经需要20秒以上，
 * 100万元素则几乎半个多小时，已经相当于无限大了，没意义。
 *
 * 第二种方案总体比第一种稍微快一点，但也没什么卵用，效率差在于如何排序
 */
public class Selection {
    //map，元素个数-->消耗时间
    static Map<Integer,Long> funMap1 = new TreeMap<>();
    static Map<Integer,Long> funMap2 = new HashMap<>();

    public static void main(String[] args) {
        //设计测试使用的n，数组
        int i =0;
        int[] ns =new int[50];
        for (int j = 0; j <50 ; j++) {
            if (j<7){
                ns[j] = 10;
            }else if (j<14){
                ns[j] = 100;
            }else if (j<21){
                ns[j] = 1000;
            }else if(j<28){
                ns[j] = 10*1000;
            }else if(j<35){
                ns[j] = 100*1000;
            }else if(j<42){
                ns[j] = 1000*1000;
            }else if(j<50){
                ns[j] = 10*1000*1000;
            }
        }
        while (i<50){
            calTheKth(ns[i]);
            i++;
        }
        System.out.println(funMap1);
        System.out.println("=======================割");
        System.out.println(funMap2);
    }

    //先排序 后取第k个
    static long calTheKth(int n){
        //使用随机数填满n个元素的数组
        int k = n/2;
        int maxs = 10*n;
        int[] arr = new int[n];
        for (int i=0;i<n;i++){
            arr[i] = (int)(Math.random()*maxs);
        }
        int[] arr1 = Arrays.copyOf(arr,arr.length);
        long begin,end,time;
        int kth;
        //A解决方案
         begin = System.currentTimeMillis();
        int[] sortedArr = BubbleSort(arr);
//        System.out.println("sortedArr排序后:"+Arrays.toString(sortedArr));
         kth = sortedArr[n-k];
         end = System.currentTimeMillis();
         time = end - begin;

        funMap1.put(n,time);


        System.out.println("第一种：kth="+kth+",time = "+time+",n = "+n);
        System.out.println("=======================================");

        //B解决方案
        begin = System.currentTimeMillis();
        int[] front = Arrays.copyOf(arr1,k);
        front = BubbleSort(front);
        for (int i=k;i<n;i++){
            front = insertNum(front,arr1[i]);
        }
        kth = front[0];
        end = System.currentTimeMillis();
        time = end - begin;
        funMap2.put(n,time);
        System.out.println("第二种：kth="+kth+",time = "+time+",n = "+n);

        return 0;
    }

    //向从小到大排序的数组插入某个数
  private static int[] insertNum(int[] arr,int k){
        if (k<=arr[0])
            return arr;
        for (int i=0;i<arr.length-1;i++){
           if ((k<arr[i+1]&&k>arr[i])||(k == arr[i])){
               for(int j=0;j<=i;j++){
                   arr[j] = arr[j+1];
               }
               arr[i] = k;
           }
        }
        return arr;
    }


    //冒泡排序 略微优化
    private static int[] BubbleSort(int[] target){
        int n = target.length;
        if(target!=null && n>1){
            for (int i=0;i<n;i++){
                boolean exchange = false;
                for (int j = n-1;j>i;j--){
                    if(target[j]<target[j-1]){
                        int temp = target[j];
                        target[j] = target[j-1];
                        target[j-1] = temp;
                        exchange = true;
                    }
                }
                if (!exchange)//如果i-->n已经有序，则直接返回
                    return target;
            }
        }
        return target;
    }

    static void pow(){
        System.out.println(Math.pow(2, 31));
    }

}
